package leetcode.Hot100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 * 有效括号组合需满足：左括号必须以正确的顺序闭合
 * https://leetcode-cn.com/problems/generate-parentheses/
 * @version 1.0
 * @date 2021/11/23 21:15
 * 1 ()
 * 2 ()() (())
 * 3 "((()))","(()())","(())()","()(())","()()()"
 * bracket 括号
 */
public class generateParenthesis {
    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
    }

    // 动态规划状态定义：List<String>
    static List<String> generateParenthesis(int n) {
        String bracket = "()";
        List<String> result = new ArrayList<>();
        result.add(bracket);
        if (n == 1) return result;
        HashSet<String> resultSet = new HashSet<>();
        for (int i = 2; i <= n; i++) {
            for (String item : result) {
                for (int j = 0; j < item.length(); j++) {
                    String newItem = item.substring(0, j) + bracket + item.substring(j);
                    resultSet.add(newItem);
                }
            }
            result.clear();
            result.addAll(resultSet);
            resultSet.clear();
        }
        return result;
    }
}
